////翻转对
////给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。
////因为不能在归并的过程中一起计算翻转对，所以要利用单调性+同向双指针计算翻转对
////在该数后面找某个数的两倍比该数小的，（降序）
////在该数前面找某个数的一半比该数大的，升序
//class Solution {
//    int[] temp;
//    int ret;
//    public int reversePairs(int[] nums) {
//        int n=nums.length;
//        temp=new int[n];
//        ret=0;
//        megerSort(nums,0,n-1);
//        return ret;
//    }
//    public void megerSort(int[] nums,int l,int r){
//        if(r<=l) return;
//
//        int mid=(l+r)/2;
//        megerSort(nums,l,mid);
//        megerSort(nums,mid+1,r);
//
//        int cur1=l;
//        int cur2=mid+1;
//        int i=l;
//        //只能根据单调性，利用同向双指针计算
//        while(cur1<=mid&&cur2<=r){
//            long tempNum1=(long)nums[cur1];
//            long tempNum2=(long)nums[cur2]*2;
//            if(tempNum1>tempNum2){
//                ret+=(r-cur2+1);
//                cur1++;
//            }else{
//                cur2++;
//            }
//        }
//        //合并排序数组
//        cur1=l;cur2=mid+1;
//        while(cur1<=mid&&cur2<=r){
//            if(nums[cur1]<=nums[cur2]){
//                temp[i++]=nums[cur2++];
//            }else{
//                temp[i++]=nums[cur1++];
//            }
//        }
//        while(cur1<=mid){
//            temp[i++]=nums[cur1++];
//        }
//        while(cur2<=r){
//            temp[i++]=nums[cur2++];
//        }
//
//        for(int j=l;j<=r;j++){
//            nums[j]=temp[j];
//        }
//    }
//}
